/**
 * Copyright 2009 cestum.org
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.almirun.common.collections
{
	import flash.events.Event;
	import flash.events.EventDispatcher;
	
	/**
	 * A basic implementation of a linked list data stucture
	 */
	public class ConcreteLinkedList extends EventDispatcher
			implements LinkedList
	{
		/**
		 * Dispatched when data in the linked list changes
		 * @eventType	flash.events.CHANGE
		 */
		[Event(name="change", type="flash.events.Event")]
		
		/**
		 * The first node in the sequence
		 */
		public function get firstNode():LinkedListNode
		{
			return _firstNode;
		}
		protected var _firstNode:LinkedListNode;
		
		/**
		 * The final node in the sequence
		 */
		public function get lastNode():LinkedListNode
		{
			return _lastNode;
		}
		protected var _lastNode:LinkedListNode;
		
		/**
		 * Inserts a node after another node
		 * @param	node	The new node to be inserted
		 * @param	before	The node after which to place the new node
		 */
		public function insertAfter(node:LinkedListNode,
				after:LinkedListNode):void
		{
			node.previousNode = after;
			node.nextNode = after.nextNode;
			
			if (null == after.nextNode)
			{
				_lastNode = node;
			}
			else
			{
				after.nextNode.previousNode = node;
			}
			
			after.nextNode = node;
			dispatchChangeEvent();
		}
		
		/**
		 * Inserts a node before another node
		 * @param	node	The new node to be inserted
		 * @param	before	The node before which to place the new node
		 */
		public function insertBefore(node:LinkedListNode,
				before:LinkedListNode):void
		{
			node.previousNode = before.previousNode;
			node.nextNode = before;

			if (null == before.previousNode)
			{
				_firstNode = node;
			}
			else
			{
				before.previousNode.nextNode = node;
			}
			
			before.previousNode = node;
			dispatchChangeEvent();
		}
		
		/**
		 * Inserts a node at the beginning of the list
		 * @param	node	The new node to insert at the beginning
		 */
		public function insertAtBeginning(node:LinkedListNode):void
		{
			if (null == firstNode)
			{
				_firstNode = _lastNode = node;
				node.nextNode = node.previousNode = null;
				dispatchChangeEvent();
			}
			else
			{
				insertBefore(firstNode, node);
			}
		}
		
		/**
		 * Inserts a node at the end of the list
		 * @param	node	The new node to insert at the end
		 */
		public function insertAtEnd(node:LinkedListNode):void
		{
			if (null == lastNode)
			{
				insertAtBeginning(node);
			}
			else
			{
				insertAfter(node, lastNode);
			}
		}
		
		/**
		 * Removes a node from the list
		 * @param	node	The node to remove
		 */
		public function remove(node:LinkedListNode):void
		{
			if (null != node.nextNode)
			{
				node.nextNode.previousNode = node.previousNode;
			}
			
			if (null != node.previousNode)
			{
				node.previousNode.nextNode = node.nextNode;
			}
			
			if (node.equals(firstNode))
			{
				_firstNode = node.nextNode;
			}
			
			if (node.equals(lastNode))
			{
				_lastNode = node.previousNode;
			}
			
			//	Remove references to allow garbage collection
			node.nextNode = node.previousNode = null;
			dispatchChangeEvent();
		}
		
		/**
		 * Adds a list to the end of this one. This method modifies the value of
		 * this object and does not return a value
		 * @param	list	The linked list to append 
		 */
		public function concat(list:LinkedList):void
		{
			if (null == list.firstNode)
			{
				return;
			}
			
			insertAfter(list.firstNode, lastNode);
			_lastNode = list.lastNode;
			dispatchChangeEvent();
		}
		
		/**
		 * Returns the list as an array
		 */
		public function toArray():Array
		{
			var arr:Array = [];
			var node:LinkedListNode = firstNode;
			
			if (null == node)
			{
				return arr;
			}
			
			arr.push(node);
			
			while (null != (node = node.nextNode))
			{
				arr.push(node);
			}
			
			return arr;
		}
		
		/**
		 * How far from the first node is from the given node. Returns -1 if the
		 * node is not in the list
		 */
		public function getNodeIndex(node:LinkedListNode):int
		{
			var idx:int = -1;
			var eachNode:LinkedListNode = firstNode;
			var i:int = 0;
			
			while (null != eachNode)
			{
				if (node.equals(eachNode))
				{
					idx = i;
					break;
				}
				
				eachNode = eachNode.nextNode;
				++i; 
			}
			
			return idx;
		}
		
		protected function dispatchChangeEvent():void
		{
			dispatchEvent(new Event(Event.CHANGE));
		}
	}
}